[LeetCode] 509. Fibonacci Number

問題描述

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).

Example:

翻譯

• 經典不敗題型
• 費式數列，通常使用 F(n)來表示數列，每一個數都是由前兩個數所構成的，頭兩個數值分別為 0,1

解題思維

1. 遞迴版本：每次呼叫 fib(N-1)+fib(N-2)，若 N 為 0 則回傳 0,1 則回傳 1，最終回傳答案
2. 迭代版本：先開好 N 個空間的陣列，頭兩個元素分別設為 1,1，透過迭代方式，最後回傳最後一個元素

解題報告

Level: Easy
Time Complexity: O(n)
Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
Memory Usage: 36.3 MB, less than 5.51% of Java online submissions for Fibonacci Number.

程式完整解題

class Solution {
    //遞迴版本
    public int fib(int N) {
         if(N<=1)
            return N;
         return fib(N-1)+fib(N-2);
    }

    //迭代版本
    public int fib(int n) {
        if(n<2){
         return n;
        }else {
          int[] ans = new int[n];
              ans[0] = 1;
              ans[1] = 1;
              for(int i=2;i<n;i++) {
                  ans[i]=ans[i-1]+ans[i-2];
              }
              return ans[n-1];
        }
    }
}